package top.humbleyuan.datastructure.linkedlist;

import java.util.Random;

/**
 * @Author HumbleYuan
 * @Date 2019/9/20 8:44
 * @Des 带随机节点的链表
 */
public class Node {

    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
    public Node(int val) {
        this.val = val;
    }

    //生成链表
    public static Node formLink(Node head,int [] vals) {
        //先构造不带随机节点的链表
        Node l = head;

        int len ;
        for(len = 0;len < vals.length;len++) {
            l.next = new Node(vals[len]);
            l = l.next;
        }
        len ++; //链表长度

        Random random = new Random();
        //再为每个链表节点生成一个随机节点
        for(int i = 0;i < len;i++) {
            Node temp = head;
            for(int j = 0 ;j < i;j++)
                temp = temp.next;

            //为random随机指向一个节点
            int randomNodeIndex = random.nextInt(len + 1) ;
            //指向空节点的情况
            if(randomNodeIndex == len) {
                temp.random = null;
                continue;
            }

            Node randomNode = head;
            for(int k = 0;k < randomNodeIndex;k++) {
                randomNode = randomNode.next;
            }
            temp.random = randomNode;

        }

        return head;

    }


}
